class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Linklist:
    def __init__(self):
        self.head = None
    """
    创建新节点newNode(target_list)，检查当前链表是否为空：
        空链表：head指向newNode
        非空链表：newNode指向原head，保证插入在头部
                head指向newNode，保证可以使用head访问
    """
    def insertAtBegin(self,data):
        newNode = Node(data)
        if self.head is None:
            self.head = newNode
        else:
            newNode.next = self.head
            self.head = newNode
    """
    在现有链表中索引值Index位置插入新节点newNode(target_list):
        索引位置在头部：执行头插insertAtBegin
        插入内部：
            建立位置变量position 初始化为0
            建立前序节点currentNone 初始化指向head，目标是插入位置节点前一位节点
            当 前序节点非空 且 位置变量不在索引位置前一位 时：前序节点和位置变量持续后移一位
            当 前序节点非空 (但 位置变量已经在索引位置前一位) ：
                初始化新节点newNode(target_list)
                newNode的next 更改 为前序节点的next，保证连续性
                前序节点的next指向newNode，实现插入
            若 位置变量在索引位置前 但 前序节点为空：
                报错：链表内不存在该插入位置，索引值超出链表长度
    """
    def insertAtIndex(self, data, index):
        if index == 0:
            self.insertAtBegin(self, data)
        else:
            position = 0
            currentNode = self.head
            while (currentNode is not None) and (position+1 != index):
                position += 1
                currentNode = currentNode.next
            if currentNode is not None:
                newNode = Node(data)
                newNode.next = currentNode.next
                currentNode.next = newNode
            else:
                print("ERROR: Index Not Present!")
    """
    在现有链表尾部插入新节点newNode(target_list):
    链表为空：头指针指向NewNode
    非空：初始化 currentNode 与 head 同 指向 头节点
        currentNode未作为尾结点(next非None)：currentNode持续后移一位
        作为尾结点：currentNode.next指向插入节点newNode
    """
    def insertAtEnd(self, data):
        newNode = Node(data)
        if self.head is None:
            self.head = newNode
            return
        currentNode = self.head
        while currentNode.next is not None:
            currentNode = currentNode.next
        currentNode.next = newNode
    """
    """
    def print(self):
        if self.head is None:
            print("The LinkList is empty")
        else:
            currentNode = self.head
            while currentNode.next is not None:
                print(currentNode.data,end=" ")
                currentNode = currentNode.next
            print(currentNode.data)


    def updateNode(self, value, index):
        if self.head is None:
            print("ERROR: The LinkList is empty")
            return
        currentNode = self.head
        position = 0
        if position == index:
            currentNode.data = value
        else:
            while (currentNode is not None) and (position != index):
                position += 1
                currentNode = currentNode.next
            if currentNode is not None:
                currentNode.data = value
            else:
                print("ERROR: Index Not Present!")


def concatenationLinklist(Llist:Linklist, LlistAno: Linklist):
    currentNode = Llist.head
    while currentNode.next is not None:
        currentNode = currentNode.next
    currentNode.next = LlistAno.head

# 测试插入与打印
ptr = Linklist()
ptr.insertAtBegin("a")
ptr.insertAtEnd("b")
ptr.insertAtEnd("c")
ptr.insertAtEnd("d")
ptr.insertAtEnd("e")
ptr.insertAtIndex('3',3)
ptr.print()
# 测试链接
ptrAno = Linklist()
ptrAno.insertAtBegin("+++")
concatenationLinklist(ptr, ptrAno)
ptr.print()
# 测试更新
ptrTest = Linklist()
ptrTest.insertAtBegin("+++")
ptrTest.updateNode("---",0)
ptrTest.print()










